'''
https://leetcode.cn/problems/reverse-linked-list/
'''

from typing import Optional

from utils import ListNode, DListNode


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

def reverse_double_list(head: Optional[DListNode]) -> Optional[DListNode]:
    prev, cur, next = None, head, head.next
    while cur:
        next = cur.next
        cur.next = prev
        cur.prev = next
        prev = cur
        cur = next
    return prev

def print_double_list(head: Optional[DListNode]) -> None:
    forward = str(head.val)
    while head.next:
        head = head.next
        forward += ' => ' + str(head.val)
    backward = str(head.val)
    while head.prev:
        head = head.prev
        backward += ' => ' + str(head.val)
    print(f'forward: {forward}')
    print(f'backward: {backward}')

l1 = DListNode(val=1)
l2 = DListNode(val=2)
l3 = DListNode(val=3)
l4 = DListNode(val=4)
l5 = DListNode(val=5)
l1.next = l2
l2.next = l3
l3.next = l4
l4.next = l5
l5.prev = l4
l4.prev = l3
l3.prev = l2
l2.prev = l1
print_double_list(l1)
new_list = reverse_double_list(l1)
print_double_list(new_list)